/*
 * 1006.合并两个排序的整数数组A和B变成一个新的数组。
 * https://www.lintcode.com/problem/merge-two-sorted-arrays/description
 * 
 * 样例
 * 给出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]
 * 
 * 挑战
 * 你能否优化你的算法，如果其中一个数组很大而另一个数组很小？
 * 
 * 2018.06.01 @jeyming
 */

package merge_two_sorted_arrays;

import java.util.Arrays;

public class merge_two_sorted_arrays {

	/**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
    public static int[] mergeSortedArray(int[] A, int[] B) {
        // write your code here
    	int a=0,b=0;
    	int number=A.length+B.length;
    	int[] newArray=new int[number];
    	Arrays.sort(A,0,A.length);
    	Arrays.sort(B,0,B.length);
    	int cnt=0;
    	for(int i=cnt;i<number&&a<A.length&&b<B.length;++i,cnt=i) {
    		if(A[a]<B[b]) {
    			newArray[i]=A[a++];
    		}
    		else if(A[a]==B[b]) {
    			newArray[i]=A[a++];
    			newArray[++i]=B[b++];
    		}
    		else {
    			//A[a]>B[b]
    			newArray[i]=B[b++];
    		}
    	}
    	while(a<A.length) {
    		newArray[cnt++]=A[a++];
    	}
    	while(b<B.length) {
    		newArray[cnt++]=B[b++];
    	}
    	return newArray;
    }
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int A[]= {1,2,3,4};
		int B[]= {2,4,5,6};
		int Result[]=mergeSortedArray(A,B);
		for(int i=0;i<Result.length;++i) {
			System.out.print(Result[i]+" ");
		}
	}

}
